package _hash

import org.junit.Assert
import org.junit.Test

/*
题型：哈希法
https://programmercarl.com/0001.%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C.html
https://leetcode.cn/problems/two-sum/description/

1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target  的那 两个 整数，并返回它们的数组下标。

输入：nums = [2,7,11,15], target = 9
输出：[0,1]

输入：nums = [3,2,4], target = 6
输出：[1,2]
*/
class leetcode_1_Kotlin {
    @Test
    fun test_1() {
        val actual = twoSum(intArrayOf(2, 7, 11, 15), 9)
        val expect = intArrayOf(0, 1)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    @Test
    fun test_2() {
        val actual = twoSum(intArrayOf(3, 2, 4), 6)
        val expect = intArrayOf(1, 2)
        Assert.assertEquals(expect.contentToString(), actual.contentToString())
    }

    private fun twoSum(nums: IntArray, target: Int): IntArray {
        /**
        题型：哈希法

        思路：
        定义一个HashMap，存放 nums 元素的 value 和index
        遍历nums，若 target - n 在Map中存在，说明找到了两个整数，若不存在，则把value 和 index 存入Map中。

         时间复杂度：O(N)
         空间复杂度：O(N)
         */
        // key = n, value = index of n at nums
        val map: HashMap<Int, Int> = HashMap()
        var key: Int

        val result: IntArray = IntArray(2)

        for (i in 0 until nums.size) {
            key = target - nums[i]
            if (map.containsKey(key)) {
                val index = map[key] ?: 0
                result[0] = index
                result[1] = i
                break
            }
            map[nums[i]] = i
        }
        return result
    }
}